package leetcode;

/**
 * @Description
 * @Author away
 * @Version V1.0.0
 * @Since 1.0
 * @Date 21.5.17
 */

public class T993 {
    public static void main(String[] args) {

        int[] root = {1, 2, 3, -1, 4, -1, 5};
        TreeNode rootNode1 = TreeNode.buildTree(root, null, 0);

        T993 t993 = new T993();
        t993.isCousins(rootNode1, 4, 5);

    }

    public boolean isCousins(TreeNode root, int x, int y) {
        if (getNodeLevel(root, x, 0) == getNodeLevel(root, y, 0)) {
            return getParentNode(root, x).val != getParentNode(root, y).val;
        }
        return false;
    }

    public int getNodeLevel(TreeNode root, int x, int level) {
        if (root.val == x) {
            return level;
        }

        if (root.left != null) {
            int nodeLevel = getNodeLevel(root.left, x, level + 1);
            if (nodeLevel != -1) {
                return nodeLevel;
            }
        }
        if (root.right != null) {
            int nodeLevel = getNodeLevel(root.right, x, level + 1);

            if (nodeLevel != -1) {
                return nodeLevel;
            }
        }
        return -1;
    }

    public TreeNode getParentNode(TreeNode root, int x) {
        if (root.val == x) {
            return null;
        }
        if (root.left != null) {
            if (root.left.val == x) {
                return root;
            } else {
                TreeNode parentNode = getParentNode(root.left, x);
                if (parentNode != null) {
                    return parentNode;
                }
            }
        }
        if (root.right != null) {
            if (root.right.val == x) {
                return root;
            } else {
                TreeNode parentNode = getParentNode(root.right, x);
                if (parentNode != null) {
                    return parentNode;
                }
            }
        }
        return null;
    }
}
